//
// Created by 11067 on 2023/3/6.
//

#ifndef WORD_LIST_CORE_GRAPH_H
#define WORD_LIST_CORE_GRAPH_H

#include <string>
#include <vector>
#include <set>
#include <queue>
#include <map>
#include <omp.h>
#include <cstring>
#include <algorithm>

#include "utils/utils.h"

#define MAX_WORD_NUM 20000


struct IntSet {
    int *arr;
    int n;
    void init(int _n) {
        arr = new int[_n];
        memset(arr, 0, sizeof(int) * _n);
        n = _n;
    }

    void dispose() {
        delete[] arr;
    }

    void insert(int x) {
        arr[x] = 1;
    }

    void erase(int x) {
        arr[x] = 0;
    }

    int count(int x) {
        return arr[x] == 0 ? 0 : 1;
    }
};

struct MyStack {
    int *arr;
    int n;
    int top;
    void init(int _n) {
        arr = new int[_n];
        n = _n;
        top = 0;
    }
    void dispose() {
        delete[] arr;
    }
    void push_back(int x) {
        arr[top++] = x;
    }
    void pop_back() {
        top--;
    }
    void copy_into(std::vector<int> &target) const {
        target.clear();
        target.reserve(top);
        for (int i = 0; i < top; ++i) {
            target.emplace_back(arr[i]);
        }
    }

};
struct Edge {
    const std::string* word;
    int begin, end;
    int idx;
};

struct Node {
    std::vector<Edge*> words_in;
    std::vector<Edge*> words_out;
    std::vector<Edge*> cycles;
};

class Graph {
public:
    //explicit Graph(std::string& str);
    explicit Graph(std::set<std::string>& words);

    //~Graph();

    bool has_cycle();

    int cnt_chains(std::vector<std::vector<const std::string*>>& chains);

    // if not used, input '\0'
    int longest_chain(char op_h, char op_t, char op_j, bool is_word, std::vector<std::string>& chain);

    // if not used, input '\0'
    int longest_chain_r(char op_h, char op_t, char op_j, bool is_word, std::vector<std::string>& chain);

private:
    Node nodes[26];
    std::set<std::string> words;
    std::vector<Edge*> edges;
    char op_h{}, op_t{}, op_j{};
    bool is_word{};

    void init();

    // in_deg[26]
    void set_in_deg(int in_deg[]);

    // for dfs_r
    std::vector<int> dfs_longest_path[26];
    int dfs_max_len[26];
    void dfs_r(int i, int now_len, IntSet vis, MyStack& path, int t_id);
    // for lock
    omp_lock_t lck;
};


#endif //WORD_LIST_CORE_GRAPH_H
